package _2022.hot100._90_子集II;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Set;

/**
 * @author： YHSimon
 * @date： 2022-08-08 19:43
 */
public class Solution {
    public List<List<Integer>> subsets(int[] nums){
        List<List<Integer>> res=new ArrayList<>();
        List<Integer> combination=new ArrayList<>();
        Arrays.sort(nums);
        dfs(res,combination,nums,0,false);
        return res;
    }

    private void dfs(List<List<Integer>> res, List<Integer> combination, int[] nums, int cur,boolean choosePre) {
        if(cur==nums.length){
            res.add(new ArrayList<>(combination));
            return;
        }


        combination.add(nums[cur]);
        dfs(res, combination, nums, cur+1, true);//选择当前的数
        combination.remove(combination.size()-1);//回溯  将当前添加的数删除
        while(cur<nums.length-1&&nums[cur]==nums[cur+1]){ // 去重，不选当前数递归时 直接跳过重复数
            cur++; //所有重复数的可能性在前面递归中均会出现
        }
        dfs(res, combination, nums, cur+1, false); // 不选当前的数
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.subsets(new int[]{1,2,3,4}));
    }
}
